package com.leetcode.no75;

import java.util.Arrays;

public class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int c1, c2, c3;
        c1 = c2 = c3 = 0;

        for (int i = 0; i < len; i++) {
            switch (nums[i]) {
                case 0:
                    c1++;
                    break;
                case 1:
                    c2++;
                    break;
                case 2:
                    c3++;
                    break;
            }
        }

        for (int j1 = 0; j1 <= c1 - 1; j1++) {
            nums[j1] = 0;
        }
        for (int j2 = c1; j2 <= c1 + c2 - 1; j2++) {
            nums[j2] = 1;
        }
        for (int j3 = c1 + c2; j3 <= c1 + c2 + c3 - 1; j3++) {
            nums[j3] = 2;
        }
    }
}


class Solution01 {
    public void sortColors(int[] nums) {
        int[] a = new int[3];
        for(int i : nums){
            a[i]++;
        }
        Arrays.fill(nums, 0, a[0], 0);
        Arrays.fill(nums, a[0], a[0] + a[1], 1);
        Arrays.fill(nums, a[0] + a[1], nums.length, 2);
    }
}

class Solution02{
        public void sortColors(int[] nums) {
            int len = nums.length;
            if (len < 2) {
                return;
            }

            // all in [0, zero) = 0
            // all in [zero, i) = 1
            // all in [two, len - 1] = 2

            // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
            // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
            // 所以下面遍历到 0 的时候，先交换，再加
            int zero = 0;

            // 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
            // 所以下面遍历到 2 的时候，先减，再交换
            int two = len;
            int i = 0;
            // 当 i == two 上面的三个子区间正好覆盖了全部数组
            // 因此，循环可以继续的条件是 i < two
            while (i < two) {
                if (nums[i] == 0) {
                    swap(nums, i, zero);
                    zero++;
                    i++;
                } else if (nums[i] == 1) {
                    i++;
                } else {
                    two--;
                    swap(nums, i, two);
                }
            }
        }

        private void swap(int[] nums, int index1, int index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
}